perm filename NOTES.EVA[LSP,JRA] blob
sn#316174 filedate 1977-11-07 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .SS(Alternatives to %3prog%*,,P253:)
C00015 00003 .SS(Extensions to %3eval%*,,P187:)
C00023 00004 .ss(Non-recursive Control Structures,,P222:)
C00032 00005 .ss(¬3eval¬* with Explicit Access,,P209:)
C00058 00006 .ss(¬3eval¬* with Explicit Control)
C00076 00007 .SS(An Evaluator for %3prog%*,,P211:)
C00109 00008 .CENT(Problems)
C00112 00009 .SS(Alternatives to %3eval%*,,P268:)
C00128 00010 .CENT(Problems)
C00130 ENDMK
C⊗;
.SS(Alternatives to %3prog%*,,P253:)
.FP
The %3prog%1 feature of LISP is an effective means for encoding iterative
algorithms, however it suffers from a few draw-backs. For example,
The label-and-%3go%1 style of control is only a slight elaboration of
the control mechanisms which are typically used to control a hardware machine,
and thus the level of description which is required
tends to obscure the actual flow of the algorithm unless
the programmer is careful.
A slight extension to conditional expressions and
conditional statements can alleviate some of the confusion which is
likely when constucting complex %3prog%1s.
.P194:
Conditional expressions are currently defined such that each
%2e%4i%1 must be a single expression.
With the introduction of side effects,
it is convenient to extend conditionals to include components of the
form: %2p%4i%3#→#%2e%4i1%3;#...#;%2e%4in%1.
This extended component is to be evaluated as follows: if %2p%4i%1 is true, then
evaluate the %2e%4ij%1's from left to right, with the value of the component to be
the value of %2e%4in%1.⊗↓This
extended conditional expression (⊗↑[Bob#69]↑) is available
in several versions of LISP: LISP#1.6 ⊗↑[Qua#72]↑,
MACLISP ⊗↑[Moo#74]↑, and INTERLISP ⊗↑[Int#75]↑.←
For example, this feature, used in %3prog%*s would allow us to replace:
.BEGIN TABIT2(10,14);
.BOXA
\\ ....
\\[%2p%41%3 → %3go[l]]
\m
\\ ...
\\return[%et%*];
\%3l\%2e%41%3;
\\%2e%42%3;
\\ ...
\\%3go[m];
.END
.PT2
.FP
with:
.BEGIN CENTER;
.PT2
... [%2p%41%3 → %2e%41%3; %2e%42%3; ... ] ...; %3return[%et%*]]
.END
.BOXB
.FP
The improved readibility is largely do to the localizing or "packaging" of
the actions with their initiators; we need not scan an arbitrarily long piece
of text to discover what the computation will be when the predicate is true.
Several languages have included more
"packaged" versions of iterative control. The motivation is similar
to that which we used in justifying recursive control: we didn't care
%6how%1 recursion was implemented, all we wished to discuss was the
%6effect%1 or %6behavior%1 of recursion.⊗↓We %6could%1 have replaced
recursive control with an appropriate combination of label-and-%3go%1's.
and a simulated stack. We will do so shortly.←
An iterative unit must allow the programmer
a reasonable degree of freedom and naturalness in expression. What should also
be recognized is that the structural unit should be amenable to analysis
to the same degree as that allowed in recursion. We must be able to state
precise properties of algorithms which use these constructs, and we should be able
to prove properties of such algorithms.
With the control of the loop structure in the
language rather than in the hands of the programmer, the
static text and the dynamic flow of the execution have a close
relationship. General use of label-and-%3go%1's and assignments
does not maintain such properties.
Our iterative control construct should therefore capture all of the essential
ingredients of an iteration, and its semantics should be restricted such that
its static text does indeed reflect its dynamic flow.
Our first example is based on the MacLISP %3do%1 ⊗↑[Moo#74]↑. With some inessential
changes, its syntax is:
.BEGIN TABIT2(17,20);GROUP;
.BOXA
\%3do\[%1<var%41%1> <init%41%1> <step%41%1>;
\\ %1<var%42%1> <init%42%1> <step%42%1>;
\\ ...
\\ %1<var%4n%1> <init%4n%1> <step%4n%1>;
\\[<pred> → <exit>]
\\ <body> ]
.BOXB
.END
.FP
The construct captures the ideas of intialization and updating of variables nicely.
Each <var%4i%1> is initialized to its <init%4i%1>-value simultaneously.
Each <step%4i%1> is a form which will be evaluated
simultaneously upon proper completion
of each cycle of the %3do%1. The <pred> is evaluated, and on giving value %et%1
the loop will terminate, returning the value of <exit>.
If <pred> gives %ef%1 then <body> is executed. This component of the %3do%1
is a %3prog%1 body; when the last statement in <body> is executed, the
<step%4i%1> forms are evaluated and assigned to the <var%4i%1>'s, and
another cycle of the %3do%1 is begun.
Since the <body> of the %3do%1 is a %3prog%1 body, the %3return%1 statement
may appear. This feature allows the dynamic flow to
diverge from the static text.⊗↓Compare this to the
behavior of free variables under dynamic binding.
From a programming point of view, being able to escape
from the static text, either for variable reference or for control
may be convenient. Whether either feature is "good#practice" is a matter of
taste.← But consider the %3do%1 version of %3member%1:
.BEGIN TABIT3(7,26,29);SELECT 3;GROUP;
.BOXA
\member <= λ[[a;l]\do\[x l rest[x];
\\\ [null[x] → %ef%*]
\\\ [eq[first[x];a] → return[%et%*]] ]
.BOXB
.END
.FP
This algorithm could be expressed without %3return%1 but the
resulting program is unnecessarily complex.
An alternative iterative construct was proposed in ⊗↑[Wis#75]↑.
.BEGIN center;SELECT 3;GROUP;
.BOXA
repeat[%1<st-list%41%1>;%3while %1<pred%41%1>; <st-list%42%1>; %3until %1<pred%42%1>; <st-list%43%1>]
.BOXB
.END
.FP
where <pred%4i%1> is a predicate, and <st-list%4i%1> is a list of
statements. The list may be empty, but may not contain %3return%1s or %3go%1s.
The semantics is as follows: <st-list%41%1> is executed; <pred%41%1> is
then evaluated and if false we exit the %3repeat%1 with %ef%1. If <pred%41%1>
is true, then we execute <st-list%42%1> and test <pred%42%1>; if <pred%42%1> is true
we exit with %et%1, otherwise we execute <st-list%43%1> and iterate the loop
beginning again at <st-list%41%1>.
For example we could write %3member%1 as:
.BEGIN TABIT3(1,15,22);GROUP;SELECT 3; turn off "←";
.BOXA
\member <= λ[[a;l]
\\repeat[\while
\\\ not[null[l]];
\\\until
\\\ equal[a;first[l]];
\\\l ← rest[l]]]
.BOXB
.END
.FP
The difficulty which we encountered with the MacLISP %3do%1 has been
alleviated, however the %3repeat%1 construct has several shortcomings
of its own. In particular, we have no means for designating
what variables are to be initialized and incremented within the loop.
Such variables must be declared and initialized external
to the %3repeat%1; also the stepping of the loop variables must be done
using the assignment statement. Similarly the power of expression on leaving
the %3repeat%1 is limited; we cannot explicitly declare what
values are to be returned. The value is that of the appropriate <pred%4i%1>.
.CENT(Problems)
.P136:
.P133:
.NL
1.##Some of the generality of %3prog%*s can be controlled
by the use of a new control structure for list operations. The
construct is called %3lit%*.⊗↓Named for %3l%1ist %3it%1erator ⊗↑[Bar#66]↑←
%3lit%1 takes three arguments: a binary function %3f%1,
a list %3l%1, and a value %3v%1.
If %3l%1 is empty, give %3v%1; otherwise apply %3f%1 to the first element of
%3l%1 and the effect of applying %3lit%1 to the remainder of %3l%1.
.GROUP
.begin INDENT 4,4
For example %3append%* could be expressed as:
.PT2;
.BEGIN CENTERIT; SELECT 3;
←append <= λ[[x;y] lit[function[concat];x;y]]
.END
.PT2
Give a non-%3prog%1 definition for %3lit%1.
.end
.APART
.GROUP
.P193:
.NL
2.##Here is another useful extension to LISP:
Instead of requiring that the body of a λ-definition
be a single expression: %9x%1 in %3λ[[#...#]#%9x%*]%1, allow bodies of the form:
%9x%41%3;#...;#%9x%4n%3%1, giving rise to λ-definitions like
%3λ[[#...#]#%9x%41%3;#...;#%9x%4n%3]%1. The application of such
a definition means: bind the λ-variables as usual, then evaluate the %9x%4i%1's
from left to right returning
as value, %9x%4n%1.
Extend the evaluator of {yonss(P6)} to handle such constructs.
.APART
.NL
3.##Give an S-expr representation for the %3repeat%1 expression and add
%3repeat%1 to %3eval%1 of {yonss(P6)}.
.pt24
.SS(Extensions to %3eval%*,,P187:)
.FP
The introduction of the %3prog%1-feature completes our
syntactic description of the
language constructs of LISP. We would like to give a new version of %3eval%1
which describes the semantics of %3prog%1s in a manner which accurately reflects
the techniques used in implementations. We could simply simulate %3prog%1 behavior
using recursive techniques, but the iterative control expressed in %3prog%1s
is an important idea in its own right and is a simple instance of
non-recursive control. A mechanism which faithfully implements such control
structures leads easily to the idea of %2⊗→generalized control structures↔←%1.
The second interesting feature introduced with %3prog%1s was the assignment
statement. Again, we could mirror most of the behavior of assignments
by careful use of the techniques of recursion and symbol tables, but such
modelling would not adequately reflect the intent
of the construct or give insight into the techniques
used in implementing such constructs. We could describe such implementations
in a low-level machine language, but such practice would only introduce
unnecessary details. Rather, we will describe an evaluator in LISP using
the techniques we have been developing. In the process we will elucidate
much more than just %3prog%1s and assignments; we will lay bare much more
of the behavior which was implicit in the previous evaluators. Those
evaluators used recursion in the explication of recursion, frequently depended on
call-by-value in the explanation of call-by-value, and suppressed much of the
detail of binding and look up. The Weizenbaum environments added more detail, but
failed to describe an explicit mechanism for the handling of partial computations,
neither showing where partial results were maintained nor how the evaluator was to
remember where it was in an expression when it had to evaluate a sub-expression.
All of this detail will come out in the new evaluator. Since the
structure of the new %3eval%1 is quite different from those
we have seen before, and since
the level of detail is more intense, we will proceed in several steps.
First we discuss some generalizations of the label-and-%3go%1
control structures. These ideas have importance in their own right when we
discuss actual interactive implementations of LISP. Next we develop
an %3eval%1 in which the handling of access structures is explicit. The
innovations in this evaluator will form the basic blocks which we will use
to model parameter passing and assignments. This evaluator will still be
recursively described, and will not handle the %3prog%1 feature. In the final
step we replace the recursion with explicit control and with this
change we have the basis for adequate treatment of non-recursive control.
Finally we present an evaluator which handles all of the %3prog%1-related
constructs.
.ss(Non-recursive Control Structures,,P222:)
.FP
On {yon(P83)} we discussed the %3go%1 construct. In that discussion we
noted that the scope of the %3go%1 was not restricted to the current %3prog%1;
we need only locate an appropriate label in a %6dynamically%1 surrounding
expression. Thus we could jump out of an expression, passing through many
intervening expressions, whereas strict recursive control requires that we
exit functions in a level-by-level fashion.
This ability to exit across many levels of computation
finds applications
at the system level in interactive LISP implementations
and is also a useful programming
feature. For example, if some extraordinary condition occurs within a
computation we might wish to abort that whole endeavor. As things currently
stand we would have to supply an additional value in the range of each
function which could occur in that computation. Each function
would have to test for that exception-value and when it is found, return that
value to the caller. This is an effective, but not elegant, solution
to the problem. Notice that this is the solution posed in our
use of %9B%1 in conjunction with strict functions.
Indeed, a more elegant solution has its origins in the early LISP debugging
tools. If a computation produced a detectable error, then it
was the responsibility of the LISP controller to print an error
message and terminate the computation. Such behavior was acceptable for
simple computations.
As computations became more complex it became clear that the occurrence of
one error need not signal the termination of %6all%1 computation.
Particularly since the expressions were available as data structures, the
opportunity for self-correcting programs existed in LISP. Thus LISP needed
a mechanism for more selective control of error messages.
The early LISP systems supplied a pair of functions named ⊗→%3errset%1↔←
and ⊗→%3err%1↔←.
The function %3errset%1 evaluates its first argument in the current context.
If no error occurs in that evaluation, the result is %3concat%1ed onto
(#) and returned. If an error does occur then the value of the %3errset%1
is %ef%1. Notice that in either case the %3errset%1 terminates. We can test
the success of our calculation by sampling the value of %3errset%1:#%ef%1
implies failure; otherwise the %3first%1 element of the result is the
true value.
The user can also force the occurrence of an "error" by calling %3err%1.
The unary function %3err%1 returns the value of its argument to the dynamically
enclosing %3errset%1 or, if there is no such %3errset%1, the value
is returned as the final value of the computation.
For example if %3err%1 is restricted to returning values in a set disjoint
from those returned by a non-"error" computation,
then the user can test the value of %3errset%1 to discover the
type of "error".
.P195:
The freedom allowed by the %3errset-err%1 combination soon became exploited
in ways not originally intended. The use of %3errset%1 and %3err%1 in
non-error-handling contexts often became quite confusing. The
MacLISP (⊗↑[Moo#74]↑) dialect includes a pair of constructs named ⊗→%3catch%1↔← and
⊗→%3throw%1↔← to be used in these situations.
%3catch%1 and %3throw%1 are both binary functions. Both first arguments
are expressions; both second arguments are interpreted
like %3prog%1 labels.
%3catch%1[<form>;<label>] evaluates its first argument in
the current context, and returns
that value, except that if during that evaluation, a %3throw[%1<form>;<label>]
with the
same <label> is evaluated, then the value of %3throw%1's <form> is returned
immediately as the value of the corresponding %3catch%1.
For example⊗↓⊗↑[Moo#74]↑←:
.BEGIN SELECT 3;GROUP;TABIT3(5,11,21);
.BOXA
\catch[\mapfirst[\function[λ[[x][x<0 → throw[x;negative];%et%3 → f[x]]]];
\\\y];
\\negative]
.BOXB
.END
.FP
Assuming %3y%1 is a list of numbers,
this expression will return a list of %3f%1 applied to each element of %3y%1
if each element of %3y%1 is non-negative,
otherwise it will return the first negative element of %3y%1.
.P262:
The %3catch-throw%1 pair are the control analog of the
%3function-funarg%1#application pair for access.
A general implementation of %3catch-throw%1 introduces a very non-recursive
control regime. The ususal implementation corresponds to allowing functional
%6arguments%1 only; if we wish to %3throw%1 into procedure activations
which have already been exited, then we must implement a control
tree similar to the environment trees
generated for functional values. The next few sections
will develop implementation techniques which will support such
tree-like implementations.
As motiviation for those techniques, recall the the "value" of a
%3prog%1 label is essentially a pointer to a segment of text
in the %3prog%1 body.
The label which appears in a %3catch%1 is evaluated similarly; in this
case the "value" is a pointer just prior to the return mechanism implemented
in the call to %3catch%1. The action of %3throw%1 searches the control tree
for a matching label and jumps to that saved value, thus returning from the
%3catch%1. If the value which a %3throw%1 returns is a %3catch%1 label,
then we have a handle into the control tree similar to that created
by a functional value when it creates a handle into an environment
tree.
.ss(¬3eval¬* with Explicit Access,,P209:)
.FP
There are two major portions of the evaluation schemes which
we should scrutinize before we discuss
implementations: the access and binding structures, and the description of
recursive control.
This section will look at access and binding.
The Weizenbaum environments give a nice graphical representation of the
access structures, but it would be instructive to express these ideas
in terms of LISP functions. This would give us an algorithm, suitable for
implementation, and would describe the mechanisms of LISP at a more detailed level
than that in the evaluators of {yonss(P6)}. The description
will involve primitive notions just as the prior %3eval%1's do, however
the level of detail which they capture will be more readily transcribed
to implementations.
As we have previously mentioned, the Weizenbaum environments leave much of the
detail of access and binding implicit; it will be a goal of this section
to fill in these details.
Recall that a Weizenbaum environment was created at function-entry time.
As we evaluated the arguments to a function, we saved the results
in some internal data structure. When all arguments were evaluated we formed
a new local block, linking it onto the front of the existing environment.
The resulting structure became the new environment.
An analysis of these steps highlights several points.
We need space
to contain the evaluated parameters, and those results are then moved
into a environment block;
therefore, if we construct the space which is to contain
those evaluated parameters like an environment block then the linking
operation need only attach that new object. This strategy is possible since
the space requirements for the evaluated parameters is known: the
block must be as long as the number of formal parameters expected.⊗↓Some LISP
systems allow discrepancies between the number of actual parameters
and formal parameters. The current scheme will accommodate that generality.←
This requirement can be ascertained by examining the definition of the
function being called. Once the block is allocated, the actual parameters
are evaluated and the results are sent to the proper slot in the
allocated block. Such a block will be called a %2destination block%1; and the
operation of placing a result in a destination will be called %2sending%1.
Once all the evaluated parameters have been sent, we %2link%1 the completed
block into the front of the current environment.
The ideas expressed in this section are an embellishment of those on {yon(P212)}.
The innovation is to allocate space for the evaluated arguments before
beginning their actual evaluation. The evaluator sends the values to
the allocated block.
.BEGIN group;
Here are the primitive routines:
.DEF
%21.%1 %3alloc_dest%1: This unary function is supplied with the formal parameter
list of a function, and supplies a new destination block with the formal
parameters placed in the name-section of the block. An internal pointer is
initialized to the first slot in the block. Thus:
.END
.BOXB
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
.BOXA;KRK
∞1 a destination block∞*
⊂ααααααα⊃
~ #αβα⊃
εαααπαααλ ↓ ∞1internal pointer∞*
~ ~ ~←$
εαααβαααλ
~ ~ ~
# # #
εαααβαααλ
~ ~ ~
%ααα∀ααα$
↑ ↑
∞1formal parameters values∞*
.BOXB
.END
.APART
.BEGIN GROUP;
.DEF
%22.%1 %3send%1: This is a binary function whose first argument is a destination
block
and whose second argument is a value to be sent. The value of %3send%1 is the
destination block. The effect of %3send%1 is to send its second argument to the
current destination slot. The internal pointer is %6not%1 updated; that is the
business of %3next%1.
.END
.BEGIN GROUP;
.DEF
%23.%1 %3next%1: This function takes a destination block as argument and moves
the internal pointer of the block to point to the
succeeding slot. The value of %3next%1 is the destination block. Thus
%3next%1 is an identity function with a side-effect.
.END
.BEGIN GROUP;
.DEF
%24.%1 %3link%1: %3link%1 takes a destination block and an environment as arguments
and links the destination block onto the front of the environment. The
resulting environment is the value of %3link%1. Since the internal pointer
is only used during the filling of the dest-block, we can assume that
%3link%1 replaces that pointer with a pointer to the previous environment.
.END
.BEGIN GROUP;
.DEF
%25.%1 %3receive%1: Sometimes we will wish to examine the result of a computation
before making a decision on how to proceed.
In particular, in conditional expressions we must
evaluate the predicate position before knowing how to handle the rest of the
conditional. The unary primitive %3receive%1 lets us look at the result of a
computation. The argument to %3receive%1 is a destination block, and the value
returned is the value in the current slot.
.END
.BOXB
.CENT(Problem)
Give a full LISP representation of destination blocks and supply the corresponding
implementations for the primitive routines, %21%1 through %25%1.
.GROUP;SKIP 3;
In the following evaluators we will freely use the extended
conditional expressions and λ-expressions introduced on {yon(P194)} and {yon(P193)}.
The first evaluator is named %3deval%1, with the "%3d%1 coming from "destination".
.BEGIN TABIT2(15,25);SELECT 3;GROUP;
.BOXA
deval <= λ[[exp;env;dest]
\[isconst[exp] → send[dest;denote[exp]];
\ isvar[exp] → send[dest;lookup[exp;env]];
\ %et%3 → deval%41%3[func[exp]; arglist[exp]; env; dest] ]]
.BOXB
.END
.BEGIN NOFILL;TABS 4,18,23,33,38,41,43,48,58,62;TURN ON "\";SELECT 3;GROUP;
.<<.BEGIN NOFILL;TABS 14,28,33,43,48,51,53,58,65;TURN ON "\";SELECT 3;GROUP;>>
.KRK
deval%41%3 <=
λ[[fun;args;env;dest]
\[atom[fun] → \[iscond[fun] → devcond[args;env;dest]
\\ isprim[fun] → execute[\fun;
\\\\\\\link[\evalargs[\args;
\\\\\\\\\env;
\\\\\\\\\alloc_dest
\\\\\\\\\\[createvars[args]];
\\\\\\\\env];
\\\\\\\dest];
\\ %et%3 →\deval[fun;env;dest];
\\\deval%41%3[receive[dest];args;env;dest] ]
\ islambda[fun] → evalargs[\bodylist[fun];
\\\\link[\evalargs[\args;
\\\\\\\\env;
\\\\\\\\alloc_dest[vars[fun]]]];
\\\\\env];
\\\\dest]
\ %et%3 → deval[fun;env;dest]; deval%41%3[receive[dest];args;env;dest] ]]
.BOXB
.END
.BEGIN TABIT2(16,21);SELECT 3;GROUP;
evalargs <= λ[[args;env;dest]
\[null[args] →dest;
\ null[rest[args]] → deval[first[args];env;dest];
\ %et%3 →\deval[first[args];env;dest];
\\next[dest];
\\evalargs[rest[args];env;dest] ]]
.PT2
execute <= λ[[fun;env;dest]send[dest;apply[fun;vals[env];( )]]]
.BOXB
.BEGIN FILL;SELECT 1;
.FP
Note that %3execute%1 resorts to %3apply%1 to handle primitive application.
.END
.APART
.GROUP
.BOXA
devcond <= λ[[args;env;dest]
\deval[pred[first[args]];env;dest];
\[receive[dest] → evalargs[condbody[first[args]];env;dest];
\ %et%3 → devcond[rest[args]; env;dest] ]]
.BOXB
.END
This new evaluator must be supplied with an initial destination as well as
being supplied with an initial symbol table. Also, since the result of any
calculation is a destination block rather than just a simple value, we should
supply a selector to extract the desired value. For example, if we designate
%3val%1 as such a selector, and designate the atom %3TLB%1 as the repository
for the top level binding then:
.BEGIN CENTER;SELECT 3;
.BOXA
eval <= λ[[exp;env] val[deval[exp;env;alloc_dest[(TLB)]]]]
.BOXB
.END
More of the details of argument handling should now be understandable:
when a function
application has been recognized, the evaluator sets up a block to hold
the results of evaluating the actual parameters. If the function is a
primitive function then the name slots are filled with some system-created
names, otherwise the λ-variables are used.
.PT24;PT24
.BEGIN GROUP;
.CENT(Problem)
Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x] eq[x;A]]%1.
.END
.PT24
.PT24
Notice that for most of the evaluation process, %3dest%1 is a passive element.
A new destination block is created on function applications, but that %3dest%1
is passed around as an argument through most of the pieces of the evaluator
without explicit modification.
That is, in most λ-bindings %3dest%1 simply gets rebound to the same object.
Since the λ-binding process is not inexpensive
it is tempting to make variables like %3dest%1, which change infrequently,
into non-local variables; they would be initialized at the outside layer
and modified
by side-effects during the evaluation. However the current value
of %3dest%1 %6does%1 need to be saved occasionally. Those occasions
correspond to the places where
%3dest%1 gets rebound to something other than %3dest%1.
We will supply two new primitives to handle explicit saving and restoring
of values:
.BEGIN def;GROUP;
%21.%1 %3save%1: This binary function would be implemented as a special form.
Its first argument is a name %3old%1, and its second argument is a value %3new%1.
The current value associated with %3old%1 is saved, and the value %3new%1 becomes
the value of %3old%1.
.END
.BEGIN def;GROUP;
%22.%1 %3restore%1: This is a unary function; its argument is a name %3name%1. The
latest value which was saved
for %3name%1 is restored. The value which %3name%1
had on entry to %3restore%1 is lost.
.END
.pt18
Using %3save%1 and %3restore%1 we could express the evaluation of a
λ-application something like:
.BEGIN;SELECT 3;TABIT2(1,37);GROUP;
.BOXA
\eval[%eR%f(%3 λ[[x;y]%9x%3][a;b] %f)%3; env] =\save[x;a];
\\save[y;b];
\\eval[%eR%f( %9x %f)%3 ;env%9'%3];
\\restore[y];
\\restore[x];
.END
.BOXB
.P200:
The implementation details of %3save%1 and %3restore%1 will not be
needed for most of our discussion, however we include some of them here for
completeness. The information which is %3save%1d and %3restore%1d is
accessible through a global variable named %3control%1. A %3save[%1<name>;<value>]
has the effect of %3concat%1-ing the current value of <name> onto the front of
%3control%1; it then sets the new value of <name> to <value>.
.BEGIN TABIT1(10); turn off "←";
.BOXA
That is:
\%3control ← concat[eval[%1<name>%3;env];control];
\set[%1<name>; %3eval[%1<value>%3;env]];%1
.BOXB
.END
.BEGIN GROUP;
.fp
Then #### %3restore%1[<name>] performs:
.BEGIN CENTER;SELECT 3;TURN OFF "←";
.pt18;
set%1[<name>%3;first[control]]; control ← rest[control]
.BOXB
.END
.END
.BEGIN TURN OFF "←";
The manipulation of %3control%1 by %3save%1 and %3restore%1 is stack-like
in LISP. That means that only the %3first%1 element of %3control%1 is accessible;
to access elements in the interior of %3control%1 requires %3restore%1-ing
down to them by sequence of "%3control%1#←#%3rest[control]%1". Once
we have removed elements from %3control%1 there is no way to access
that information again.
The %3control%1-structure
is not accessible as a data structure to the same degree of generality
as is the access structure. The closest analogy to %3function-funarg%1 is
the %3catch-throw%1 pair. However now that %3control%1 is explicit
we can begin to describe extensions to LISP which %6will%1 allow us to capture %3control%1
like %3function%1 captures %3env%1.
.END
Given %3save%1 and %3restore%1 we can rewrite %3deval%1 and its subfunctions
to access non-local representations of variables used in the current %3deval%1.
Thus the evaluator becomes a function of no arguments; it %6knows%1 where to
find the values and it knows how to save and restore those variables.
The result is an evaluator which has even %6fewer%1 implict operations
than %3deval%1.
.BEGIN SELECT 3;TABIT2(17,22);GROUP;
.P196:
.BOXA
deval%9'%3 <= λ[[]\[isconst[] → send[denote[]];
\ isvar[] → send[lookup[]];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\deval%41%3[];
\\restore[args];
\\restore[fun] ]]
.BOXB
.END
A few points should be noted now. We will be using the same names
as we did in %3deval%1 for all subfunctions of %3deval%9'%1. The difference
will be that here those functions will %6know%1 where their arguments are to be
found; they need not be explicitly passed in. Thus %3send[denote[]]%1
means that %3denote%1 extracts a value from the representation in %3exp%1
and %3send%1 knows that it is to send its value to %3dest%1.
With this new evaluator we can define %3eval%1 as:
.BEGIN TABIT2(9,25);SELECT 3;TURN OFF "←";
.BOXA
\eval <= λ[[x;y]\fun ← ();
\\args ← ();
\\exp ← x;
\\env ← y;
\\dest ← alloc_dest[(TLB)];
\\deval%9'%3[];
\\val[dest]]
.END
.BOXB
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 16,30,43;
.KRK;BOXA
.FP
%1Here is the remainder of %3deval%9'%1:
%3
deval%41%3 <= λ[[]\[isatom[] → \[iscond[] → devcond[];
\\ isprim[] → \save[env;env];
\\\save[dest;alloc_dest[createvars[]]];
\\\evalargs[];
\\\link[];
\\\restore[dest];
\\\execute[];
\\\restore[env];
\\ %et%3 → deval%42%3[] ]
\ islambda[] → \save[env;env];
\\save[dest;alloc_dest[vars[]];
\\evalargs[];
\\link[];
\\restore[dest];
\\save[args;bodylist[]];
\\evalargs[];
\\restore[args];
\\restore[env];
\ %et%3 → deval%42%3[] ]]
.END
.BEGIN SELECT 3;TABIT1(18);group;
.PT2
deval%42%3 <= λ[[ ]\save[exp;fun];
\deval%9'%3[];
\restore[exp];
\save[fun;receive[]];
\deval%41%3[];
\restore[fun] ]
.BOXB
.FILL;SELECT 1;
.FP
We introduced %3deval%42%1 to capture the computation to be performed
when the function-position is not recognized as either a λ-expression, a conditional,
or a primitive.
Note that we perform %3save[env;env]%1 in a couple of places in %3deval%41%1.
This is necessary to save the current value of %3env%1 since %3link%1
modifies %3env%1. Indeed, the sequence: save %3env%1 and %3dest%1, %3evalargs%1,
%3link%1, and restore %3dest%1 can be simplified to:
save %3dest%1, %3evalargs%1, followed by %3link%9'%1.
where:
.BEGIN CENTER;SELECT 3;
.BOXA
link%9'%3 <=λ[[] set_int[dest;env];rotate[env;first[control];dest]]
.BOXB
.END
.FP
and %3set_int%1 sets the internal pointer of the dest-block to
the current environment, and %3rotate[x;y;z]%1 moves the contents of %3x%1 to %3y%1,
contents of %3y%1 to %3z%1, and contents of %3z%1 to %3x%1.
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 19,24,35;
.BOXA;KRK
evalargs <= λ[[]\[emptyargs[] → ( );
\ singlearg[] → \save[exp;first[args]];
\\\deval%9'%3[];
\\\restore[exp];
\ %et%3 →\save[exp;first[args]];
\\deval%9'%3[];
\\restore[exp];
\\next[];
\\save[args;rest[args]];
\\evalargs[];
\\restore[args] ]]
.END
.BOXB
The discussions surrounding this evaluator tacitly assume that a deep binding strategy
is being implemented. That assumption is not necessary. The final
shallow binder of {yonss(P134)} can be incorporated in the framework
of these latest evaluators. The key alterations involve the rebinding
of the value cells inside %3deval%41%1 when %3islambda%1 is true.
We leave the modifications as a problem for the reader;
and we postpone the treatment
of %3function%1 until {yonss(P225)} and {yonss(P228)}.
Note also that we are never interested in the value returned from a
call on a sub-function in the evaluator; all values are passed
explicity from their creator to a destination. We might say that
%3deval%9'%1 never returns a value. In the next section we will
build an evaluator which never returns at all.
.CENT(Problems)
.NL
1.##Write the new version of %3devcond%1.
.NL
2.##Examine the %3save-restore%1 sequences in %3deval%9'%1 and its
sub-functions for possible inefficiencies. That is, are all the
saves and restores necessary or could explicit assignments to some of
the non-local variables speed things up?
.NL
3.##Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.NL
4.##Revise the new evaluator to use shallow binding. You may restrict
your solution to the case of simple function application without
%3function%1.
.ss(¬3eval¬* with Explicit Control)
.FP
Recursion and call-by-value are used to guide the flow of control
in a LISP evaluator. We have started to explore the implementation
of call-by-value, and now we wish to discuss the implementation of
recursion.
It is not necessary to understand %6how%1 recursion works to understand
recursion; that understanding %6is%1 necessary when we wish to implement
recursion.
The mechanisms used in the implementation of any concept
must be of a higher level of detail than the mechanism being implemented.
We cannot use recursion to implement recursion. The basic
purpose of recursive control in the evaluator is to describe
what computation to perform next and to describe where to go when finished.
The evaluator of this section
will rely on explicit directions to tell it what to do next.
The idea is closely related to the logical notion of
%2⊗→continuation↔←s%1 (⊗↑[Str#74a]↑, ⊗↑[Rey#72]↑, ⊗↑[Fis#72]↑, ⊗↑[Hew#76]↑)
and thus we will use that terminology here.
In the evaluators of this section we will use the destination to tell where the
result of the current computation is to be put, and use the continuation
to tell what the next computation will be.
Note that the computations in %3deval%1 are basically of two categories:
.BEGIN nl;GROUP;
%21.%1##Simple transformations like sending, building %3dest%1 blocks, or
selecting components of expressions. These computations are non-recursive, requiring
a bounded amount of computation.
.APART
.nl
%22.%1##Recursive calls on the evaluator or its subfunctions. These computations
can be arbitrarily complex.
.END
It is the recursive computations which we wish to examine. One of the
implications
of a function call is that we have further computation to be performed
%6after%1 the call is completed. It is the responsibility of the evaluator
to remember where a computation has been interrupted so that
it may pick up where it left off, after completing the call.
One of the major problems in implementing evaluators is "how to remember".
If the function being called is a simple calculation of type %21.%1 above,
then we could replace the call with a copy of the body of the definition
where we have replaced each occurrence of a formal parameter with the
appropriate actual parameter; this works nicely.
Indeed making such formal substitutions at runtime is sufficient
for computations of type %22.%1 as well.
However the solution in this case is not sufficiently efficient.
Previous evaluators "remembered" what was to be done
either by using recursion, as in %3eval%1
({yonss(P6)}), or by explicit sequencing as in %3deval%1.
We now propose to explicitly %2pass along%1 information about what to
do after the current computation is completed. This information
is called
the %2continuation%1.
The first evaluator of this section is %3ceval%1;⊗↓%3c%1 for
%3c%1ontrol or %3c%1ontinuation←
it is a modification
of %3deval%9'%1 of {yon(P196)}.
It takes a single argument %3c%1 which is a continutation.
The continutation is passed along as a funarg structure until %3ceval%1
has completed its current computation. At that time %3c%1 is executed.
For example we transform %3deval%9'%1 into %3ceval%1 by forming a continuation
from that portion of %3deval%9'%1 which follows the call on %3deval%41%1. Thus:
.BEGIN SELECT 3;TABIT2(16,20);GROUP;
.BOXA
ceval <= λ[[c]\[isconst[] → send[denote[]];c[];
\ isvar[] → send[lookup[]];c[];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\ceval%41%3[function[ev1]] ]]
.PT2
ev1 <= λ[[ ] restore[args]; restore[func]; c[] ]]
.BOXB
.END
.FP
For the simple cases we just execute the continuation after the %3send%1;
when we have a function application we make up a new continuation.
When %3ceval%41%1 is finished with the function application
it executes %3ev1%1; that does the %3restore%1 operations and then performs
the saved continuation.
Note the use of %3function%1. The non-local variable %3c%1 in %3ev1%1
represents the continuation passed into %3ceval%1. Therefore %3c%1
must be found in the environment of the body of %3ceval%1 not
in the environment which is current when %3ev1%1 is applied.
As before, %3eval%1 is expressible with the new evaluator:
.BEGIN TABIT2(2,18);SELECT 3;TURN OFF "←";
.BOXA
\eval <= λ[[x;y]\fun ← ();
\\args ← ();
\\exp ← x;
\\env ← y;
\\dest ← alloc_dest[(TLB)];
\\ceval[function[λ[[ ] val[dest]]]] ]
.BOXB
.END
.FP
Transforming the sub-functions of %3deval%9'%1 is reasonably straightforward:
the segment of program below a call on one of the recursive parts of the
evaluator is given a name; a new continuation is made,
similar to the process of creating %3ev1%1; then
the transformation process is applied to each new continuation.
For example, here's %3ceval%41%1:
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 17,30,31,42;
.BOXA;KRK
ceval%41%3 <= λ[[c]\[isatom[] → \[iscond[] → devcond[c];
\\ isprim[] → \save[env;env];
\\\\save[dest;alloc_dest[createvars[]]];
\\\\evalargs[function[ev2]];
\\ %et%3 → ceval%42%3[];
\ islambda[] → \save[env;env];
\\\save[dest;alloc_dest[vars[]]
\\\evalargs[function[ev5]];
\ %et%3 → ceval%42%3[]] ]]
.END
.BEGIN NOFILL;
.PT2
.krk
%3ceval%42%3 <= λ[[ ] save[exp;fun]; ceval[function[ev3]]]%1
.END
.boxa
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 14,42,56,67;
.KRK
ev2 <= λ[[ ]\link[];\ev3 <= λ[[ ]\restore[exp];
\restore[dest]; \\save[fun;receive[]];
\execute[];\\ceval%41%3[function[ev4]]]
\restore[env];
\c[]]
.APART
.GROUP
.boxa
ev4 <= λ[[ ] restore[fun]; c[]]\ev5 <= λ[[ ]\link[];
\\\restore[dest];
\\\save[args;bodylist[]];
\\\evalargs[function[ev6]]]
.PT2;pt2
.apart
ev6 <= λ[[ ]\restore[args];
\restore[env];
\c[]]
.BOXB
.END
.BEGIN GROUP;
.CENT(Problems)
.NL
1.##Continuations can also be used as general programming tools. For example,
evaluate %3fact%42%3[2]%1 where:
.ONCE INDENT 4,4;
%3fact%42%3 <= λ[[x] fact%42%9'%3[x;function[λ[[x] x]]]]
.TABIT3(4,23,35);
.PT2
\%3fact%42%9'%3 <= λ[[n;f]\[zerop[n] → f[1];
\\ %et%3 → fact%42%9'%3[\sub1[n];
\\\function[λ[[x] f[times[n;x]]]]]]]
.END
.NL
2.##Write the new version of %3devcond%1 and %3evalargs%1.
.NL
3.##Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.PT24
.PT24
The final transformation step is analogous to that which we performed
in moving
from %3deval%1 to %3deval%9'%1: we remove the argument to %3ceval%1 and
pass the continuation explicitly in a non-local variable named %3cont%1.
This new evaluator is named %3ceval%9'%1:
.BEGIN SELECT 3;TABIT2(17,22);GROUP;
.BOXA
ceval%9'%3 <= λ[[ ]\[isconst[] → send[denote[]]; cont[];
\ isvar[] → send[lookup[]]; cont[];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\save[cont;function[ev1]];
\\ceval%41%3[] ]]
.PT2
ev1 <= λ[[ ] restore[args]; restore[func]; restore[cont]; cont[] ]]
.BOXB
.END
.FP
We can remove more control structure from the evaluator by noting
that executing the continuation, "%3cont[]%1", and executing the explicit calls
on the evaluator's subfunctions are two manifestations of the same phenomenon.
In the first case we restore to a variable and then execute the variable as a function
application;
in the second, we execute a known call. We can replace these two
actions by a common action if we always execute from the variable %3cont%1 and replace calls
like "%3ceval%41%3[]%1" with the sequence:
.BEGIN CENTER;select 3; turn off "←";
.BOXA
save[cont;function[ceval%41%3]]; cont[]
.BOXB
.END
.FP
Notice that when we make this last %3save%1 we know that the current value
of %3cont%1 is %3ev1%1. Notice also that when we execute %3cont[]%1 we
enter %3ceval%41%1 and therefore within this call on %3ceval%41%1,
%3cont%1 %6is%1 %3ceval%41%1. All this discussion can be simplified if we
think a bit about the purpose of continuations: we will need to make note
of what the continuation should be %6after%1 the current computation is
finished; and we will need to set %3cont%1 to designate which computation
to perform now. We therefore introduce a binary primitive %3save_cont%1 which
will save its first argument such that %3restore%1 can restore it
to %3cont%1 at the
appropriate time; %3save_cont%1 will set %3cont%1 from its second argument.
.BEGIN SELECT 3;CENTER;TURN OFF "←";
.BOXA
save_cont <= λ[[x;y] cont ← x; save[cont;y]]
.BOXA
.END
.FP
We can remove the calls %3cont[]%1, and perform the execution outside
%3ceval%9'%1 using a simple loop:
.BEGIN TABIT3(14,30,32);GROUP;SELECT 3;
.P208:
.BOXA
\loop <= λ[[] prog[[]
\\l\cont[]
\\\go[l] ]]
.BOXB
.END
.FP
Each function executed by %3cont[]%1 will perform some simple operations
like %3send%1 or %3alloc_dest%1, and then will exit, setting %3cont%1
to a function name. The next pass around, %3loop%1 will execute
the new %3cont%1. After slight reorganization to eliminate some
%3save-restore%1 operations on %3cont%1, we have:
.BEGIN SELECT 3;TABIT2(18,23);GROUP;turn off "←";
.BOXA
ceval%9''%3 <= λ[[ ]\[isconst[] → send[denote[]]; restore[cont];
\ isvar[] → send[lookup[]]; restore[cont];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\save_cont[quote[ev1];quote[ceval%41%3]] ]]
.PT2
ev1 <= λ[[ ] restore[args]; restore[func]; restore[cont] ]]
.BOXB
.END
.P204:
.FP
Notice the use of %3quote%1 rather than %3function%1.
In the previous evaluators we used %3function%1
since we had to save the current environment; but the continuation
%3c%1 was the
only free variable which was in jeopardy. In %3ceval%9''%1 we have explicitly
saved the continuation using %3save_cont%1, and thus %3quote%1 plus the
proper use of %3restore%1 can replace %3function%1. We will also
introduce an abbreviation, writing %9`%3xx%1 for %3quote[xx]%1.⊗↓This
abbreviation is used in several implementations of LISP. See {yon(P157)}.←
.BEGIN TURN ON "\";NOFILL;KRK;TABS 5,28,37,48;SELECT 3;TURN OFF "←";group;
.BOXA
%1Finally, here's %3eval%1:
%3
.PT2
\eval <= λ[[x;y] catch[\prog[[ ]\fun ← ();
\\\args ← ();
\\\exp ← x;
\\\env ← y;
\\\dest ← alloc_dest[(TLB)];
\\\save_cont[\%9`%3λ[[]throw[val[dest]; out]]];
\\\\%9`%3ceval%9''%3];
\\\loop[]];
\\out]]
.END
What has been gained by these transformations of the original %3eval%1?
We have made the mechanisms which were implicit in LISP very explicit.
We have described the implementations of LISP's access and control
requirements in terms of very simple computations. We now have
developed enough detail that we can give a faithful implementation description of
all of LISP including the %3function%1 and
%3prog%1 constructs.
.BEGIN GROUP;
.CENT(Problems)
.NL
1.##Could we use statements like %3save_cont[ev1;eval%41%3]%1 rather than %3save_cont[%9`%3ev1;#%9`%3eval%41%3]%1#?
.NL
2.##Using the new evaluator, sketch the evaluation of %3f[A]%1 where:
%3f#<=#λ[[x]#eq[x;A]]%1
.END
.SS(An Evaluator for %3prog%*,,P211:)
.FP
The evaluator in this section will be the definitive interpreter for LISP
throughout the rest of this book. It will handle the applicative subset
of LISP as well as handling %3prog%1 related constructs.
.P198:
We need to add more mechanism to handle %3prog%1.
For example the execution of the %3return%1 statement requires that we
locate dynamically surrounding %3prog%1s. The %3go%1 must also locate
the latest %3prog%1 which surrounds the %3go%1 and contains the desired label.
The evaluator needs to know when we are evaluating a conditional expression
and when we are evaluating a conditional statement; if we are (immediately) in
a %3prog%1 then it's a conditional statement, otherwise it's a conditional
expression.
All of this information could be discovered by the evaluator using the currently
supplied information, however the evaluator can be made more efficient
by adding a bit more explicit information. Most of the additions involve
%3prog%1-entry, %3go%1, and %3return%1 and will therefore be presented
when we discuss that part of the evaluator. The only addition we will make now
will be introduction of a variable %3type%1 which is set to %3PROC%1
when we begin an evaluation of an application, and is set to %3PROG%1
when we enter a %3prog%1.
We will also rework some of our current sub-functions to improve
readability.
Since sequences of %3save%1s happen frequently in the evaluators
we introduce a new procedure named %3save%9'%1 which acts like
a sequence of calls on %3save%1 for arguments other than %3cont%1.
In this latter case, a call on %3save_cont%1 is simulated.
Similarly we introduce an iterated version of %3restore%1 named %3restore%9'%1.
.CENT(Problem)
Write %3restore%9'%1 and %3save%9'%1 as macros which expand to calls on
%3save%1 and %3restore%1.
.PT24
.PT24
.PT24
Here's the new %3peval%1:
.BEGIN SELECT 3;TABIT3(17,22,28);GROUP;turn off "←";
.PT2
peval <= λ[[ ]\[isconst[] → send[denote[]];restore[cont];
\ isvar[] → send[lookup[]];restore[cont];
\ %et%3 →\save%9'%3[\fun;func[];
\\\args;arglist[];
\\\cont;#%9`%3ev1;#%9`%3peval%41%3] ]]
ev1 <= λ[[ ] restore%9'%3[args;func;cont] ]]
.BOXB
.END
.P201:
.FP
It is the responsibility of %3peval%1 to recognize the occurrence
of one of the basic forms: a variable, a constant, or a function application.
Discovering the structure of an application is the business of %3peval%41%1.
We need to know whether the function position represents a call-by-value
function or a special form. So far the only special form we recognize is
%3cond%1;⊗↓Actually %3quote%1 is also a special form which we recognize,
however its recognition is handled within %3isconst%1.←
however many of the constructs which %3prog%1 introduced
are special forms. We could add a collection of recognizers %3issetq%1, %3isgo%1,
%3isprog%1, etc., to augment the existing %3iscond%1. Instead we would
rather add a device similar to %3isprim%1 but instead of handling the call-by-value
primitives with the underlying evaluator, we wish to handle special forms with
our own pieces of %3peval%1. We need a predicate named %3isspec%1
to recognize occurrences of special forms and
will need to add functions to %3peval%1 to execute the appropriate
programs when %3isspec%1 is true. We will do this by introducing a
global table called %3spectbl%1. The name components of the
table will be the names for special forms; the value components of %3spectbl%1
will be the names of functions which will evaluate the corresponding special
form.⊗↓In the next chapter we will see a more efficient way to recognize and
execute special forms.←
Then we can write:
.BEGIN SELECT 3;GROUP;TABIT2(5,24);
.BOXA
\isspec <= λ[[ ][null[nassoc[fun;spectbl]] → %ef%3; %et%3 → %et%3]
.PT2
\nassoc <= λ[[x;l]\[null[l] → ( );
\\ eq[x;name[first[l]]] → first[l];
\\ %et%3 → nassoc[x;rest[l]]]
.BOXB
.END
To execute the appropriate routine we need only put the name in the variable
%3cont%1 and %3loop%1 will do the rest. We can load %3cont%1 by:
.BEGIN CENTER;SELECT 3; TURN OFF "←";
.BOXA
cont ← valspec[ ]; %1where:### %3valspec <= λ[[ ]value[nassoc[fun;spectbl]]]
.BOXB
.END
.FP
For example, with %3spectbl%1 bound to %3((COND DEVCOND))%1,
our previous %3ceval%41%1 would work quite nicely as:
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 18,31,40;turn off "←";
.KRK
.BOXA
ceval%41%3 <= λ[[ ]\[isatom[] → \[isspec[] → cont ← valspec[ ];
\\ isprim[] → \save[env;env];
\\ ... ] ... ]]
.BOXB
.END
Before introducing %3peval%41%1 we should say a bit about the inefficiency
involved in the %3isspec%1-%3valspec%1 pair. We already noted that
the linear search encoded in %3assoc%1 is unnecessarily inefficient.
However the present predicate-function pair is even more wasteful;
if %3isspec%1 %6is%1 true we perform %3nassoc[fun;spectbl]%1 twice.
A more efficient computation might save the result of the first
call on %3nassoc%1 in a temporary variable %3t1%1 and if %3isspec%1
is true, move the %3value%1-part of %3t1%1 to %3cont%1. Thus:
.BEGIN SELECT 3;GROUP;TABIT2(5,22);TURN OFF "←";
.P219:
.BOXA
\isspec <= λ[[ ]\t1 ← nassoc[fun;spectbl]]
\\[null[t1] → %ef%3; %et%3 → %et%3] ]
.PT2
%1with:###%3valspec <= λ[[ ] value[t1]]
.BOXB
.END
.FP
This is a useful programming trick but does not add to the clarity of the
program. In {yonss(P214)} we shall see a more subtle, but related trick.
.BEGIN SELECT 1;FILL;
What follows is the remainder of the evaluator interspersed with commentary.
The main function is %3peval%41%1; it handles function applications.
The application is
either a call-by-value application or it is a special form. An instance
of the first requires evaluation of the argument list and then evaluation
of the procedure body. If the application is a special form then
the evaluation is handled by a special piece of the evaluator, using
the mechanism described above. The call-by-value applications are either primitive
applications or are anonymous function applications.
If the form is not recognizable then
the function-position is evaluated
until a function object %6is%1 recognized. At that
time, the function is applied to its argument list.
.END
.BEGIN GROUP;TURN ON "\";NOFILL; TABS 17,30,32,39,45,49;turn off "←";
.<<BEGIN GROUP;TURN ON "\";NOFILL; TABS 17,28,33,37,42;turn off "←";>>
.BEGIN SELECT 1;FILL;
The anomalous situation involves the application of a %3funarg%1; though
it is possible to handle this case as a primitive, it is more instructive
to present it in detail. Here is %3peval%41%1:
.END
.KRK
.P203:
.BOXA
%3peval%41%3 <= λ[[ ]\[isatom[] → \[isspec[] → cont ← valspec[ ];
\\ isprim[] → save%9'%3[\env;env;
\\\\\\dest;alloc_dest[createvars[]];
\\\\\\cont; %9`%3ev2; %9`%3evalargs];
\\ %et%3 → save%9'%3[exp;fun;cont; %9`%3ev3; %9`%3peval];
\ islambda[] → \save%9'%3[\env;env;
\\\\dest;alloc_dest[vars[];
\\\\cont; %9`%3ev5; %9`%3evalargs];
\ isfunarg[] →\prog[[x;y]
\\\\x ← args;
\\\\args ← bodylist[second[fun]];
\\\\y ← env;
\\\\env ← third[fun];
\\\\save%9'%3[\env;env;
\\\\\args;x;
\\\\\dest;alloc_dest[vars[second[fun]]];
\\\\\env;y;
\\\\\cont; %9`%3ev7; %9`%3evalargs]];
\ %et%3 → save%9'%3[exp;fun; cont; %9`%3ev3; %9`%3peval] ]]
.BOXB
.END
.BEGIN GROUP;TURN ON "\";NOFILL; TABS 9,26,35;turn off "←";
.BOXA
.KRK
The functions %3ev2%1 through %3ev8%1 handle the control in %3peval%41%1:
.PT2
.SELECT 3;
.P232:
.BEGIN CENTER;
ev2 <= λ[[ ] link[]; restore[dest]; execute[]; restore%9'%3[env;cont]]
.END
.PT2
%1This function passes the evaluation to the body of the primitive.%1
.APART
.GROUP
.PT2
.BEGIN CENTER;
%3ev3 <= λ[[ ] restore[exp]; save%9'%3[fun;receive[];cont; %9`%3ev4; %9`%3peval%41%3]]
.END
.BEGIN SELECT 1;FILL;
.FP
%3ev3%1 is the return point if we have to evaluate the function position of a form.
When %3ev3%1 is called the result of that evaluation is in the current dest-slot.
A %3receive%1 gets the value; we then pass the new form back to %3peval%41%1.
.END
.PT2
.BEGIN CENTER;select 3;
ev4 <= λ[[ ] restore%9'%3[fun;cont]]
.END
.PT2
.BEGIN CENTER;select 3;
ev5 <= λ[[ ] link[]; restore[dest]; save%9'%3[args;bodylist[]; cont; %9`%3ev6; %9`%3evalargs]]
.END
.BEGIN FILL;SELECT 1;
.boxb
.FP
%3ev5%1 handles the evaluation of the body of a λ-expression. Since we are
allowing multiple-bodied λ-expressions ({yon(P193)}), we pass the %3bodylist%1
to %3evalargs%1. If we were restricting ourselves to single-bodied expressions,
then passing %3body%1 to %3peval%1 would suffice.
.END
.PT2
.BEGIN CENTER;select 3;
ev6 <= λ[[ ] restore%9'%3[args;env;cont]]
.END
.APART
.END
.PT2
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 19,24,39;TURN OFF "←";
.KRK
.BEGIN FILL;SELECT 1;
.FP
The next four functions handle the evaluation of a sequence of expressions.
If the sequence is empty, then there is nothing to do. If there is a single
argument then evaluate it and restore the continuation.
Otherwise evaluate the first one using
%3peval%1 (sending its result to %3dest%1) and then execute %3ev11%1.
At %3ev11%1 we update the destination block using %3next%1 and get set to
evaluate the next argument.
.END
.PT2
.P231:
evalargs <= λ[[]\[emptyargs[] → restore[cont];
\ %et%3 → \save[exp;first[args]];
\\cont ← %9`%3ev9 ]]
.END
.PT2
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 14,20,27;turn off "←";
.KRK
ev9 <= λ[[ ]\[singlearg[] → \save_cont[ %9`%3ev10; %9`%3peval];
\ %et%3 →\save_cont[ %9`%3ev11; %9`%3peval] ]]
.PT2
ev10 <= λ[[ ] restore%9'%3[exp;cont]]
.PT2
ev11 <= λ[[ ]\ next[];
\ args ← rest[args];
\ exp ← first[args];
\ cont ← %9`%3ev9 ] ]
.END
.PT24
.PT24
.BEGIN GROUP;
.CENT(Problem)
Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.END
.PT24;PT24
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 17,22,34;turn off "←";
.KRK
.P233:
.BEGIN FILL;SELECT 1;
The combination of %3evcond%1 and %3cond1%1 handle conditional expressions.⊗↓%1See
the problem on {yon(P197)}.←
%3evcond%1 sets up the evaluation of the predicate position such that the
computation will continue at %3cond1%1. When that evaluation is completed %3cond1%1
%3receive%1s the result. If %et%1 is received then the consequent part of that
conditional clause is evaluated. Note that we use %3evalargs%1 here since
we allow extended conditionals ({yon(P194)}).
If %ef%1 is received we go back to %3evcond%1 with the remaining part of the
conditional.
.END
.BOXA
evcond <= λ[[ ]\[emptyargs[] →\err[NO_TRUE_COND_CLAUSE];
\\\cont ← %9`%3ev1;
\ %et%3 → \save_cont[ %9`%3cond1; %9`%3peval];
\\exp ← pred[first[args]] ]]
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 16,21,28;turn off "←";
.PT2
.KRK
cond1 <= λ[[ ]\[receive[] → \args ← conseq[first[args]];
\\\save_cont[ %9`%3ev1; %9`%3evalargs];
\ %et%3 →\args ← rest[args];
\\cont ← %9`%3evcond ]]
.END
.BOXB
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 22,27,38;turn off "←";
.KRK
.BEGIN FILL;SELECT 1;
The next four functions deal with functional arguments.
If the argument is a primitive, then we just %3quote%1 it; the assumption
is that primitives only access local variables and therefore don't need to save the
environment. An expression which is already %3funarg%1-ed is passed as is
since it is aready closed and therefore has no free variables.
If it is a λ-expression, we make a %3funarg%1; otherwise we evaluate the
function until we discover its character.
.END
.BOXA
evfunction <= λ[[ ]\fun ← first[args];
\[isprim[] → send[mkquote[fun]];restore[cont];
\ islambda[] → send[mkfunarg[fun;env]];restore[cont];
\ isfunarg[] → send[fun];restore[cont];
\ %et%3 → \save_cont[ %9`%3fun1; %9`%3peval];
\\exp ← fun ]]
.PT2
fun1 <= λ[[ ] send[mkfun[receive[ ]]; cont ← %9`%3ev1]
.BOXB
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,30,39;turn off "←";
.KRK
.SELECT 1;
.FP
The functions %3ev7%1 and %3ev8%1 control the application of a %3funarg%1.
.SELECT 3;
.BOXA
ev7 <= λ[[ ]\restore[env];
\link[];
\restore%9'%3[dest;args];
\save_cont[ %9`%3ev8; %9`%3evalargs] ]]
.PT2
ev8 <= λ[[ ] restore%9'%3[env;cont]]
.BOXB
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 17,23,39;turn off "←";
.KRK
.BEGIN FILL;SELECT 1;
Special functions are needed to handle explicit calls on the evaluator:
%3eval%1[<form>;<env>]. We set up a destination to receive the values
of <form> and <env>, and ask %3evalargs%1 to evaluate these arguments.
The results of the computation are seen by %3ev12%1; this function sets up
the call on %3peval%1.
.END
.BOXA
eveval <= λ[[ ]\save%9'%3[\env;env;
\\dest;alloc_dest[createvars[(G1 G2)]];
\\cont; %9`%3ev12; %9`%3evalargs]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 16,23,39;turn off "←";
.KRK
.PT2
ev12 <= λ[[ ]\exp ← first_dest[];
\env ← second_dest[];
\restore[dest];
\save_cont[ %9`%3ev13; %9`%3peval]]
.PT2
ev13 <= λ[[ ] restore%9'%3[env;cont]] (%9≡%3 ev8)
.END
.BOXB
.P205:
.FP
There is a second form of call on %3eval%1 which is useful. If we
write %3eval%1[<form>], then the <form> is evaluated in the environment
which exists at the point of call. See problem on {yon(P206)}.
.BEGIN SELECT 1;FILL
The remainder of the evaluator involves the %3prog%1 related
constructs.
Several new ideas are involved. As we discussed on {yon(P198)},
we must be able to determine
whether or not we are executing within a %3prog%1: we introduced
%3type%1 to handle this.
Also every expression or statement in LISP has a value. Since we are always
%3send%1-ing values, we must have a destination to receive the values
created by %3prog%1#statements: we will introduce a dummy destination which
will always receive the value of any statement. This destination is named
%3bb%1, for "bit#bucket".
Finally, we must handle assignment statements. The innovation here
is that the %3send%1 goes to some pre-existing destination and destroys the
current value: we use a primitive %3mkdest%1 whose effect is to
generate a destination pointer to the slot which is to receive the value of
the right-hand-side of the assignment.
In %3evsetq%1
we use a function %3lookup%9'%1 which is similar to %3lookup%1 except
that it returns a pointer to the slot containing a value, rather than
returning the value in the slot.
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 18,24,41;turn off "←";
.SELECT 1;
Here are the evaluators for %3setq%1 and %3set%1:
.SELECT 3;
.KRK
.BOXA
evsetq <= λ[[ ]\save%9'%3[\dest;mkdest[lookup%9'%3[first[args]]];
\\cont; %9`%3setq1; %9`%3peval];
\exp ← second[args]]
.PT18
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,22,41;turn off "←";
.KRK
setq1 <= λ[[ ]\λ[[x]\restore[dest];
\\send[x];
\\cont ← %9`%3ev1 ][receive[ ]]
.PT2
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 16,30,39;turn off "←";
.KRK
evset <= λ[[ ]\save%9'%3[args;args; cont; %9`%3set1; %9`%3peval];
\exp ← first[args] ]
.PT2
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,30,39;turn off "←";
.KRK
set1 <= λ[[ ]\restore[args];
\args ← mkass[receive[];rest[args]];
\cont ← %9`%3evsetq ]
.END
.BOXB
.BEGIN SELECT 3;TURN ON "\";NOFILL; TABS 18,24,40;turn off "←";
.BEGIN SELECT 1;FILL;group;
The %3prog%1 evaluator, %3evprog%1, must handle all of the control
structures which can occur within a %3prog%1. Besides ordinary recursion, we
can have %3go%1s and %3return%1s. The %3go%1 must be able to search the
control chain for the appropriate label, and the %3return%1 must find the
dynamically enclosing %3prog%1.
To handle either of these eventualities, we %3save%1 some additional information
when we enter a %3prog%1. First we save the current state of the computation;
this will allow the %3return%1 to %3restore%1 everything as it leaves the %3prog%1.
Next we make a new %3env%1 which has bound all the %3prog%1#variables to %3(#)%1.
We save %6that%1 %3env%1, since a non-local %3go%1 will want to restore that
%3env%1 as it returns for execution. Finally we create a %3golist%1 which is a list
of all points in the %3prog%1 which have labels. This construct allows
us to discover quickly which labels are present in the %3prog%1 and where they
are.⊗↓If it weren't for the existence
of anonymous %3prog%1s and function-modifying functions, we could put
the responsibility of making the go-list
on "<=".← After
all this is done we are ready to execute the first line of the
%3prog%1#body.
.END
.BOXA
.group;
.KRK
evprog <= λ[[ ]\save%9'%3[\exp;exp;
\\env;env;
\\dest;alloc_dest[prog_vars[args]];
\\fun;fun;
\\args;prog_body[args];
\\type;PROG];
\link[];
\save%9'%3[\env;env;
\\golist;mkgolist[args]];
\cont ← %9`%3line ]
.apart
.boxb
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 26,30;turn off "←";
.KRK
mkgolist <= λ[[body] prog[[z]
\a\[null[body] → return[z];
\\ islabel[first[body]] → z ← concat[body;z] ]; ⊗↓%1Note that this program
handles multiply-labeled statements.←%3
\\body ← rest[body];
\\go[a] ]]
.BOXB
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,20,36;turn off "←";
.BEGIN SELECT 1;FILL;
The actual execution of each line of a %3prog%1#body is controlled by the
pair %3line%1 and %3line1%1. Their behavior is similar to that
of %3evalargs%1.### %3line%1 examines the next expression;
if there is no next statement, we exit with %3(#)%1 using %3prog_exit%1;
if the next statement is a label, it is ignored; otherwise we prepare to
evaluate the expression, setting the destination to %3bb%1.
.END
.KRK
.boxa
line <= λ[[ ]\[null[args] → prog_exit[( )];
\ islabel[first[args]] → args ← rest[args];
\ %et%3 → \exp ← first[args];
\\dest ← bb;
\\save_cont[ %9`%3line1; %9`%3peval] ]]
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 16;turn off "←";
.KRK
.PT2;pt2
line1 <= λ[[ ]\args ← rest[args];
\cont ← %9`%3line ]
.BOXB
.SELECT 1;FILL;
.FP
Note that we don't change %3cont%1 in %3line%1 when we see a label; we just
leave it at %3line%1 and %3loop%1 does the rest.
.BOXB
.END
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 19,30,40;turn off "←";
.BEGIN FILL SELECT 1;
We call %3prog_exit%1 to return %3(#)%1 when the body of the %3prog%1 is empty.
Thus
the discussion of %3prog_exit%1 involves the semantics of %3return%1.
Of the two control mechanisms, %3return%1 is simpler than %3go%1.
Recalling the discussion of %3save%1 on {yon(P200)},
we need to look through the %3control%1-list for the last block
designating a %3prog%1 entry. We %3restore%1 to that saved
state and set %3control%1 to that prior point.
.END
.boxa
.KRK
evreturn <= λ[[ ]\exp ← first[args];
\save_cont[ %9`%3ret1; %9`%3peval] ]
.PT2;pt2
ret1 <= λ[[ ] prog_exit[receive[]]]
.PT2;pt2
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 23;turn off "←";
.KRK
prog_exit <= λ[[val]\control ← find_prog[control];
\restore%9'%3[type;args;fun;dest;env;exp;cont];
\send[val] ]
.BOXB
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,28;turn off "←";
.BEGIN SELECT 1;FILL;
The %3go%1 statement is a bit more complicated.
When a %3go%1 statement is recognized, we look back through the dynamic
chain to find the first occurrence of the desired label. If we are in a %3prog%1
we check the current %3golist%1; if the label is not found, or if we are not
immediately in a %3prog%1, we look for the latest %3golist%1 and
search it. We continue this process until we discover the label. At that time we
restore the environment to that which encloses the label,
reset %3control%1, and continue the computation
at that point.
.END
.KRK
.boxa
evgo <= λ[[ ]\exp ← first[args];
\[isconst[] →err[BAD_PROG_LABEL];
\ not[isvar[]] → \save_cont[ %9`%3go1; %9`%3peval]
\ %et%3 → control ← prog_go[control;exp] ]]
.PT2;pt2
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 7,16,19,39,71;turn off "←";
.<<.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 26,31,52,57;turn off "←";>>
.KRK
prog_go <=
λ[[cntrl;exp]
\prog[[ ]\a\[eq[type;PROG] →\[check_go[exp;golist[cntrl]] →\restore[env];
\\\\\cont ← %9`%3line;
\\\\\return[cntrl];
\\\\ %et%3 → cntrl ← find_go[rest[cntrl]]; go[a] ];
\\\ %et%3 → cntrl ← find_go[cntrl]; go[a] ]]]
.PT2
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 27,39;turn off "←";
.KRK
check_go <= λ[[lab;glist]\[null[glist] → %ef%3;
\ eq[lab;first[first[glist]]] → args ← rest[first[glist]];%et%3;
\ %et%3 → check_go[lab;rest[glist]] ]]
.BOXB
.END
The origins of the interpreter presented here can be traced from several
sources: ⊗↑[Bla#71]↑, ⊗↑[Con#73]↑, ⊗↑[Sus#75]↑, ⊗↑[Ste#76b]↑.
.CENT(Problems)
.NL
1.##This problem involves the %3escape%1 expression discussed in ⊗↑[Rey#72]↑
and implemented in the University of Paris's LISP ⊗↑[Gre#75]↑.
We introduce the form:
.BEGIN CENTER;SELECT 3;
escape%1[<function>; <form%41%1>; ...;<form%4n%1>]
.pt2;pt2
.END
.ONCE INDENT 4,4;
with the following semantics: we evaluate the <form%4i%1>'s from left to right,
returning the value of <form%4n%1> unless we encounter an application involving
<function>. If such an application %6does%1 appear we perform that application
and immediately return the resulting value as the value of the %3escape%1 expression.
.PT2
.ONCE INDENT 4,4;
Extend our latest evaluator to recognize and execute the %3escape%1
expression.
.NL
2.##The semantics of %3go%1 specified that the argument would be evaluated
if it were a function application, however the current %3peval%1
does not handle this case. Correct that oversight.
.P197:
.NL
3.##Extend %3evcond%1 to handle conditional statements.
.NL
4.##On {yon(P200)} we discussed the implementation of
%3save%1 and %3restore%1. Implement %3save%1 and %3restore%1 for %3peval%1.
.NL
5.##Write %3find_go%1 and %3find_prog%1.
.NL
.P206:
6.##Revise %3eveval%1 to handle calls on %3eval%1 with either one or two
arguments. See {yon(P205)}.
.NL
7.##Refer to the problem involving multiple %3setq%1's on {yon(P259)}.
There you were asked to implement that feature using macros.
Either implement a macro facility in %3peval%1 or explicitly introduce
such a multiple assignment feature. You may implement that feature
as either a sequential assignment or a parallel assignment.
.NL
8.##Recall our discussion of the general %3catch-throw%1 pair on {yon(P262)}.
Implement these functions in %3peval%1.
.SS(Alternatives to %3eval%*,,P268:)
.FP
We have seen a lot of evaluators for LISP. We should at least look
a bit at other possibilities for describing computational behavior.
Indeed, what is "computation"? When we are given an expression to evaluate
we are really simulating the application of simplification and substitution rules.
The simplification rules tell us when an expression can be replaced
by another expression; typically we think of the replacing expression
as being "simpler" than the replaced expression. Thus %3car[(A#.#B)]%1
can be replaced by %3A%1, or %3[%et%1#→#2;#...]%1 can be replaced by %32%1.
The substitution rules typically allow us to replace a procedure call
with an appropriately instantiated copy of the procedure body.
Thus a computation involving %3append[(A#B);(2#3)]%1 is identical to
that obtained by replacing the occurrence of
%3append[(A B);(2 3)]%1
.PT2
.BEGIN SELECT 3;TABIT2(47,56);
%1with%3####### [null[(A B)] → (2 3); %et%3 → concat[\first[(A B)];
\append[\rest[(A B)];
\\(2 3)]]]
.BOXB
.END
.FP
The result of such a substitution is usually a candidate for further substitutions
and simplifications.
The collection of simplification and substitution rules is called the reduction rules
for the language. Given an expression, a computation
is said to terminate when
there are no further reduction rules applicable and the reduced expression
is a constant of the language. That reduced expression is the value of the
original expression.
The difficulties with these schemes come from both practical and theoretical
considerations.
The direct application of reduction rules is quite inefficient:
making textual substitutions is expensive. Instead we developed the ideas of symbol tables
to contain the bindings of the variables, rather than perform the actual
substitutions.
The theoretical difficulty appears since, at any time in a computation, there
may be more than one reduction rule which is applicable. A further difficulty
is that one sequence of reductions may terminate, while another sequence of reductions
is non-terminating. We have seen this phenomenon in previous discussions of
call-by-value versus ⊗→call-by-name↔←, inner-most versus outer-most, and
normal order reductions versus applicative order reductions.
Though
LISP opted for the call-by-value interpretation of expressions, it is possible
to develop a call-by-name evaluator. Call-by-name implies that we substitute
the unevaluated actual parameters for the formal parameters.
As in %3eval%1, we need not make explicit substitutions;
appropriate use of symbol tables will simulate the action,
but now, when we build a symbol table on entry to a λ-expression
we bind the actual expressions to the λ-variables.
When we encounter a variable in the body of the expression
we evaluate the actual parameter. The difficulty is that an actual parameter
itself
may contain variables, and those variables need to be interpreted
in the binding environment. This means that we must bind
%3funarg%1-like expressions to the formal parameters.
Most of %3eval%4name%1 is like %3eval%1 of {yonss(P6)}, so we only
sketch the interesting parts. Assume the %3funarg%1-expression we manufacture
has two components, the %3expr%1-component, and the %3env%1-component.
We can implement %3eval%4name%1 by simply changing the symbol table orgainzation,
supplying new versions of %3lookup%1 and %3mkenv%1. See {yon(P212)} and {yon(P218)}.
.BEGIN CENTERIT;GROUP;select 3;tabit3(5,20,49);
.BOXA
\alloc <= λ[[vars] ()]
.PT2
\send <= λ[[var;val;dest] concat[mkent[var;val];dest]
.PT2
\link <= λ[[dest;env] concat[dest;env]]
.PT2
lookup <= λ[[var;env] l%9'%3[var;first[env];rest[env]]
.PT2
l%9'%3 <= λ[[n;bl;env]\[null[bl] → l%9'%3[n;first[env];rest[env]];
\\ eq[n;name[first[bl]] → eval[\expr[value[first[bl]]];
\\\envir[value[first[bl]]]];
\\ %et%3 → l%9'%3[n;rest[bl];env] ]]
.BOXB
.END
.FP
One advantage of such an evaluator is that it will not evaluate
a parameter until it actually needs it, whereas %3eval%1 evaluates
all parameters at function entry time. If an actual parameter is not
used in the computation and the computation of that parameter
fails to terminate, then %3eval%4name%1 will terminate
while %3eval%1 will not.
There are disadvantages to %3eval%4name%1. Every occurrence of a variable
within the body of the function will involve a re-evaluation of the
corresponding actual parameter. If there are no side-effects in the computation
then these repeated computations are an unnecessary expense. Several people
(⊗↑[Wad#71]↑, ⊗↑[Vui#74]↑, ⊗↑[Pac#73]↑, ⊗↑[Hen#76]↑, ⊗↑[Fri#76a]↑) have suggested
modifications to %3eval%4name%1 to reduce the inefficiency.
The basic idea,
described as %2⊗→call-by-need↔←%1, is to proceed in the %3eval%4name%1 style until the first
use of a variable. At that time we evaluate the actual parameter, and
modify the symbol table,
%6replacing%1 the actual parameter with its value. Further references to that
variable simply get the value. Obviously the scheme
will not work correctly if side-effects are present.
We leave it to the reader to supply the details of %3eval%4need%1; see
{yon(P199)}.
We now explore a different kind of modification to LISP. This one is
grounded more in practical experience with the programming language,
though the results do have theoretical interest. It has been noted
that programmers frequently wish to return more than one value as the result of
a function application. The standard alternatives in LISP are either
to make global assignments
from within the body of the function, or to return a list of the desired values
making it the responsibility of the calling program to select the proper
components. Neither alternative is particularly compelling. Programming with
extensive
side-effects tends to lead to obscure programs
and may incur unnecessary complications in debugging;
see {yonss(P168)}. Passing lists back as values
requires much additional computation: someone must build the list; someone
must tear it apart. It is also disturbing that the operation being modelled,
--multiple-values--, is not recognizable as a construct. This is a similar
complaint to that we raised in discussing labels-and-%3go%1s versus an
iterative construct.
Our goal is realizable by a slight extension of the re-interpretation
of conditional expressions
and multiple-bodied
λ-expressions ({yon(P194)},#{yon(P193)}).
.GROUP;
.FP
We will interpret the form:
.BEGIN CENTER
.PT2;
%2p%4i%3#→#%2e%4i1%3; ... %2e%4in%3
.PT2;
.END
.FP
to
return the %2e%4ij%1-values to the calling function in a left-to-right
order. If the calling program is single-valued then the value it sees is
the value of %2e%4in%1. This is compatible with our current interpretation.
.APART;
.GROUP;
.FP
The evaluation of:
.BEGIN CENTER;
.PT2
%3λ[[#...#] f%41%*[#...#];#...;#f%4n%*[#...#]]%1
.END
.PT2
.FP
will be interpreted similarly.
.APART
For example ⊗↑[Fri#76b]↑ discusses a multiple-valued function named
%3sigmasum%1. This function is to take a list of numbers and return three
items: the length of the list, the sum of the numbers in the list, and
the sum of the squares of the numbers in the list.
In our notation %3sigmasum%1 can be expressed as:
.BEGIN SELECT 3; GROUP;TABIT3(21,29,39);
.BOXA
sigmasum <= λ[[x]\[null[x] → 0;0;0;
\ %et%3 → λ[\[z%41%3;z%42%3;z%43%3]\add1[z%41%3];
\\\plus[first[x];z%42%3];
\\\plus[times[first[x];first[x]];z%43%3] ]
\\[sigmasum[rest[x]]] ]]
.BOXB
.END
.FP
Notice that we use an anonymous λ-expression to spread the multiple values at the
level of the caller.
Another example is a solution to the %3samefringe%1
problem#⊗↑[Hew#74]↑: determine whether or
not the terminal nodes of two trees are the same, respecting order, but
irrespective of tree structure.⊗↓There are many "solutions" to this problem;
the simplest is to flatten the trees first, then use %3equal%1. Indeed,
there are many "problems"; the most accurate formulation requires that
no %3cons%1 operations be done. For more details and interesting
discussions see ⊗↑[Gre#76]↑, ⊗↑[Hen#76]↑, ⊗↑[And#76a]↑, and ⊗↑[Fin#76]↑.← Thus:
.BEGIN CENTERIT;SELECT 3;group;
.BOXA
←samefringe[(A (B (C))); (A B C)] = %et
%1but←%3samefringe[(A (B C)); (A C B)] = %ef%1
.END
.BEGIN SELECT 3;TABIT3(25,30,45);group;
.boxa
samefringe <= λ[[x;y]\[null[x] → null[y];
\ %et%3 → \λ[[z%41%3;z%42%3;z%43%3;z%44%3]\[eq[z%41%3;z%43%3] → samefringe[z%42%3;z%44%3];
\\\ %et%3 → %ef%3]]
\\ [fringe[x];fringe[y]] ]
.END
.PT2
.APART;
.GROUP;
.BEGIN SELECT 3;TABIT3(17,24,34);
fringe <= λ[[x]\[atom[first[x]] → first[x]; rest[x];
\ %et%3 → \λ[[y;z] y;\[null[z] → rest[x];
\\\ %et%3 → cons[z; rest[x]] ] ]
\\ [fringe[first[x]]] ] ]
.BOXB
.END
.FP
In this solution, %3samefringe%1 is single-valued but uses values from a multiple-valued
function. The two values from %3fringe[x]%1 are spread into %3z%41%1 and %3z%42%1
and the values from %3fringe[y]%1 are spread into %3z%43%1 and %3z%44%1.
.APART;
.BEGIN GROUP;
It is easy to write an evaluator for such multiple-valued expressions.
Here is a sketch of the basic parts:
.BEGIN SELECT 3;TABIT3(19,31,40);
.BOXA
meval <= λ[[x;e]\[isconst[x] → list[denote[x]];
\ isvar[x] →list[lookup[x;e]];
\ iscond[x] → mevcond[condbody[x];e];
\ %et%3 → mapply[fun[x];mevlist[arglist[x];e];e] ]]
.boxa
.END
.APART
.GROUP
.BEGIN SELECT 3;TABIT3(27,38,53);
mapply <= λ[[fn;args;e]\[isprim[fn] →list[apply[fn;args;e]]
\ islambda[fn] → mevlist[\bodylist[fn];
\\\mkenv[vars[fn];args;e] ]
\ %et%3 → mapply[eval[fn;e];args;e] ]]
.boxa
.END
.APART
.GROUP
.BEGIN SELECT 3;TABIT3(20,31,40);
mevlist <= λ[[l;e]\[null[l] → ();
\ %et%3 → append[meval[first[l];e]; mevlist[rest[l];e]] ]]
.boxa
.END
.APART
.GROUP
.BEGIN SELECT 3;TABIT2(21,63);
mevcond <= λ[[l;e]\[null[l] → ();
\ first[meval[pred[first[l]];e]] → mevlist[\conseq[first[l]];
\\env];
\ %et%3 → mevcond[rest[l];e] ]]
.BOXB
.END
.END
.CENT(Problems)
.NL
1.##Complete the specification of %3eval%4name%1.
.NL
.P199:
2.##Complete the specification of %3eval%4need%1. To do this, you may
assume the existence of a binary function named %3stuff%1 whose first argument
%3x%1 is
the a name in the symbol table, and whose second argument %3y%1 is a value.
%3stuff%1 is to replace the current binding of %3x%1 with %3y%1.
.NL
3.##Modify %3peval%1 to handle multiple-valued functions.
.NL
4.##Recall problem 2 on {yon(P221)} dealing with the analysis of
%3lookup%1. Include call-by-name and call-by-need in your
analysis.
.NL
5.##Using the results of the previous problem, make up a table
whose rows are labeled with the binding implementations: "deep"
"shallow", "Weizenbaum", "need", and "name"; and whose
columns are labeled with the prmitives: %3alloc%1, %3link%1, %3send%1,
and the primitives for %3lookup%1. Supply the entries.